package com.javabasic.algorithm.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * @author xiongmin
 * @version 0.0.1
 * @description Created by work on 2021/11/6 10:53 上午
 * @see [268. Missing Number](https://leetcode-cn.com/problems/missing-number/)
 */
public class MissingNumber {

    /**
     * 解法一：暴力+Set
     * @param nums
     * @return
     */
    public int missingNumber(int[] nums) {
        int len = nums.length;
        Set<Integer> numsSet = new HashSet<>(len);
        for (int i = 0; i < len; i++) {
            numsSet.add(nums[i]);
        }
        for (int i = 0; i <= len; i++) {
            if (!numsSet.contains(i)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 解法二：利用前n项和通项公式
     * @param nums
     * @return
     */
    public int missingNumber2(int[] nums) {
        int len = nums.length;
        int sum = len*(len+1)/2;
        for (int i = 0; i < len; i++) {
            sum -= nums[i];
        }
        return sum;
    }

    /**
     * 解法三：利用异或位运算求解
     * 原理：1^2^...^n ^ 1^2^...^n = 0, 如果其中又一个少掉了的话，那么他就是缺少的那一个
     * @param nums
     * @return
     */
    public int missingNumber3(int[] nums) {
        int len = nums.length;
        int result = 0;
        for (int i = 0; i < len; i++) {
            result ^= nums[i];
            result ^= (i+1);
        }
        return result;
    }
}
